home *** CD-ROM | disk | FTP | other *** search
/ Internet Publisher's Toolbox 2.0 / Internet Publisher's Toolbox.iso / internet / ntserver / wtsource / hash.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-02-15  |  3.6 KB  |  110 lines
  1. /* hash table routines.  not very general.
  2.  * -brewster
  3.  */
  4.  
  5. /* Copyright (c) CNIDR (see ../COPYRIGHT) */
  6.  
  7.  
  8. #ifndef HASH_H
  9. #define HASH_H
  10.  
  11.  
  12. #define DEFAULT_NUMBER_OF_BUCKETS 65536L
  13. #define DEFAULT_NUMBER_OF_ELEMENTS 131072L
  14.  
  15. #define MAX_KEY_SIZE 20 /* this is the string length, so add 1 */
  16.  
  17. typedef struct hash_entry{
  18.   char key[MAX_KEY_SIZE + 1];    /* the key.  Must be first */
  19.   long next;    /* index of the next entry in the contents */
  20.  
  21.  
  22.   /* This part is usage dependent.  Sucks that it is hard coded. (this 
  23.    * was done for efficiency. C sucks.)
  24.    * however, this can be made to be somewhat flexible, by pulling this out
  25.    * into a different .h file, and redefining the structure for different 
  26.    * purposes.  This can be done in the same application since all the 
  27.    * hashtable code cares about is the key and next values.
  28.    * (actually, not quite, take out array refs to contents in hash.c
  29.    *  and replace by explicit multiplies and it will work).
  30.    */
  31.   
  32.   long number_of_occurances;    /* total for the whole db */
  33.   unsigned char* memory_ptr;        /* what will go into the next block */
  34.   unsigned char* current_memory_ptr;    /* the fill ptr into memory_ptr */
  35.   long memory_size;        /* the size of memory_ptr */
  36.   long current_doc_id;        /* the last document-id in memory_ptr
  37.                  * this will change a page pointer eventually
  38.                  */
  39. } hash_entry;
  40.  
  41. typedef struct hashtable{
  42.   long number_of_buckets;    /* number of buckets */
  43.   long buckets_mask;        /* a mask for fast bitwise and'ing */
  44.   long element_size;        /* sizeof the element to be stored 
  45.                    (including th hash_entry_header) */
  46.   long number_of_elements;    /* total number of elements hashed */
  47.   long max_number_of_elements;    /* size of the contents buffer in elements */
  48.  
  49.   long *buckets;        /* array of longs, each an index into contents
  50.                  * -1 is an empty entry. */
  51.   hash_entry* contents;        /* pointer to hashtable memory */
  52.  
  53. } hashtable;
  54.  
  55.  
  56. #ifdef __cplusplus
  57. /* declare these as C style functions */
  58. extern "C"
  59.     {
  60. #endif /* def __cplusplus */
  61.  
  62.  
  63. /* number_of_buckets must be a power of 2, 
  64.       if -1 then it defaults to DEFAULT_NUMBER_OF_BUCKETS.
  65.    number_of_elements is the number of expected elements that will be hashed.
  66.    element_size must be the sizeof the element to be put in the hashtable 
  67.        (not including hash_entry_header).
  68.    returns NULL if an error
  69.  */
  70. hashtable *make_hashtable _AP ((long number_of_buckets, 
  71.                  long number_of_elements,
  72.                  long element_size));
  73.  
  74. /* returns a pointer to the element stored or NULL if none. */
  75. hash_entry *get_hash _AP ((char *key, hashtable *htable));
  76.  
  77. /* puts a copy of the element into the hashtable.
  78.    Returns a pointer to the new element.
  79.  
  80.    This does not check to see that the key has not already been added. */
  81. hash_entry *put_hash _AP ((char *key, hashtable *htable, hash_entry *element));
  82.  
  83. /* not implemented yet 
  84. boolean rem_hash _AP ((char *key, hashtable *htable));
  85.  */
  86.  
  87. /* removes contents without freeing memory.
  88.    returns true if successful, false otherwise */
  89. boolean clr_hashtable _AP ((hashtable *htable));
  90.  
  91. /* removes contents and free's memory for the hastable.   
  92.    returns true if successful, false otherwise */
  93. boolean free_hashtable _AP ((hashtable *htable));
  94.  
  95. long hashtable_count _AP ((hashtable *htable));
  96.  
  97. /* sorts the contents of elements of the hastable.
  98.    this destroys the hashtable */
  99. boolean sort_hashtable _AP ((hashtable *htable));
  100.  
  101. void analyze_hashtable_distribution _AP ((hashtable * htable));
  102. void print_hashtable _AP ((hashtable *htable));
  103.  
  104.  
  105. #ifdef __cplusplus
  106.     }
  107. #endif /* def __cplusplus */
  108.  
  109. #endif /* nded HASH_H */
  110.